package com.jacklei.link;

import javax.swing.undo.CannotUndoException;
import java.awt.*;
import java.util.function.Predicate;

//单链表
public class SinglyLinkedLists {

    class Node<T>{
        public T value;
        public Node next;

        public Node(T value) {
            this.value = value;
        }
    }
    public static void main(String[] args) {

    }

    //链表反转(使用递归)
    public static Node recursiveReverseList(Node head){
        if(head == null || head.next == null) return head;
        Node newHead = recursiveReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    //链表反转(使用传统的指针思想)
    public static Node reverse(Node head){
        if(head == null) return head;
        Node per = head;
        Node off = head.next;
        head.next =null;
        while (off == null){
            Node cru = per;
            per = off;
            off = off.next;
            per.next = cru;

        }
        return per;
    }

    //判断链表是否为循环链表，是返回链表的切入点 ，不是返回null；
    public static Node hasCycle(Node head){
        if(head == null) return head;
        //从头一起开始移动
        Node slow = head;
        Node fast = head;

        //先判断fast 再判断 fast.next 防止 NullPointerException
        while (fast != null || fast.next != null) {
            if (slow == fast) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        //看是否为循环链表
        if(fast == null && fast.next != null) return null;
        //是循环链表
        fast = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;

    }

}
